1. Field of the Invention
The present invention relates generally to congestion control during data transfer and, more particularly, to systems and methods for performing efficient random early drops at the head of a packet buffer.
2. Description of Related Art
Conventional network devices, such as routers, relay streams of data through a network from a source to a destination. Typically, the network devices include one or more memory subsystems to temporarily buffer data while the network devices perform network-related functions, such as route processing or accounting.
A data stream may be considered a pipe of data packets belonging to a communication between a particular source and one or more particular destinations. A network device may assign a variable number of queues (e.g., where a queue may be considered a logical first-in, first-out (FIFO) buffer) to a data stream. For a stream with n queues, the relationship of queues and streams may be represented by:
      stream    bandwidth    =            ∑      0              n        -        1              ⁢                  ⁢                  queue        bandwidth            .      
A problem that may arise in the use of queues is that congestion occurs if data builds up too quickly in the queues (i.e., data is enqueued at a faster rate than it is dequeued). Network devices typically address this problem by notifying sources of the packets of the congestion. This notification sometimes takes the form of dropping more recent packets received from the sources.
Conventional congestion avoidance techniques are replete with problems, however. For example, determining which sources to notify of the congestion can be difficult. Global synchronization can result if all sources are notified to reduce their output at the same time. Another problem involves determining when to notify the sources of the congestion. Delayed notifications can lead to reduced throughput.
As a result, there is a need for systems and methods for efficiently processing and buffering packets in a network device.